import heapq


def nthUglyNumber(n: int) -> int:
    factors = [2, 3, 5]
    seen = {1}
    heap = [1]

    for i in range(n - 1):
        curr = heapq.heappop(heap)
        for factor in factors:
            if (nxt := curr * factor) not in seen:
                seen.add(nxt)
                heapq.heappush(heap, nxt)

    return heapq.heappop(heap)



if __name__ == '__main__':
    print(nthUglyNumber(15))
    print(nthUglyNumber(1))

